Decision Problem

定义 Definition（中文）

decision problem（判定问题/决策问题）：指一种计算问题，其输出只有两种可能结果，通常是“是/否”（true/false）。在计算复杂性与可计算性理论中，常用来研究某类问题是否可被算法解决、以及需要多少计算资源。

发音 Pronunciation（IPA）

/dɪˈsɪʒən ˈprɑːbləm/

例句 Examples

A yes-or-no question is a decision problem.
“是或否”的问题就是一个判定问题。

In computational complexity, many optimization tasks are first rewritten as a decision problem to classify their difficulty.
在计算复杂性理论中，许多优化任务会先改写成判定问题，以便对其难度进行分类。

词源 Etymology（中文）

decision 来自拉丁语词根，含“裁决、决定”之意；problem 源自希腊语，指“要解决的难题”。组合成 decision problem 时，强调“要做出二选一裁决的问题”，即输出只有两类结果（是/否）的形式。该用法在20世纪数理逻辑、可计算性与计算机科学的发展中被固定下来。

相关词 Related Words

• Decision
• Problem
• Predicate
• Algorithm
• Computability
• Complexity
• NP-Complete
• Undecidable

文学与经典著作 Literary Works（出现或常见讨论）

• Alan Turing, On Computable Numbers, with an Application to the Entscheidungsproblem（1936）
• Martin Davis, Computability and Unsolvability（1958）
• Michael Sipser, Introduction to the Theory of Computation（常用于讲解判定问题与复杂性分类）
• Michael R. Garey & David S. Johnson, Computers and Intractability（讨论将问题表述为判定问题以研究NP完全性）